package previous.Test_0215;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //最大岛屿面积
    int m,n;
    boolean[][] vis;
    int count;
    int ret;
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    public int maxAreaOfIsland(int[][] grid) {
           m=grid.length;
           n=grid[0].length;
           vis=new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j]==1 && !vis[i][j]){
                    int count=0;
                    vis[i][j]=true;
                    dfs(grid,i,j);
                    ret=Math.max(count,ret);
                }
            }
        }
        return ret;
    }
    public void dfs(int[][] grid,int i,int j){
        //进去一次算一次面积
        vis[i][j]=true;
        count++;
        for (int k = 0; k < 4; k++) {
            int x=dx[k]+i;
            int y=dy[k]+j;
            if(x>=0 && x<m && y>=0 && y<n && grid[x][y]==1 && !vis[x][y]){
                dfs(grid, x, y);
            }
        }
    }
    //被围绕的区域
    //正难则反
    int m1,n1;
    int[] dx1={0,0,1,-1};
    int[] dy1={1,-1,0,0};
    public void solve(char[][] board) {
         m1=board.length;
         n1=board[0].length;
        for (int i = 0; i < m1; i++) {
            if(board[i][0]=='O' ){
                dfs2(board,i,0);
            }
            if(board[i][n1-1]=='O'){
                dfs2(board,i,n1-1);
            }
        }
        for (int j = 0; j < n1; j++) {
            if(board[0][j]=='O' ){
                dfs2(board,0,j);
            }
            if(board[m1-1][j]=='O'){
                dfs2(board,m1-1,j);
            }
        }
        for (int i = 0; i < m1; i++) {
            for (int j = 0; j < n1; j++) {
                if(board[i][j]=='.') board[i][j]='O';
                else if(board[i][j]=='O') board[i][j]='X';
            }
        }
        }
        public void dfs2(char[][] board,int i ,int j){
               board[i][j]='.';
            for (int k = 0; k < 4; k++) {
                int x=dx1[k]+i;
                int y=dy1[k]+j;
                if(x>=0 && x<m1 && y>=0 && y<n1 && board[x][y]=='O' ){
                    dfs2(board, x, y);
                }
            }
        }
        //太平洋大西洋水流问题
        int m2,n2;
    boolean[][] v;
    boolean[][] s;
    int[] dx2={0,0,1,-1};
    int[] dy2={1,-1,0,0};
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        m2=heights.length;
        n2=heights[0].length;
        v=new boolean[m2][n2];
        s=new boolean[m2][n2];
        List<List<Integer>>  ret2=new ArrayList<>();
        //易出错，最好画图
        for (int i = 0; i < n2; i++) {
            dfs3(heights,0,i,v);
        }
        for (int j = 0; j < m2; j++) {
            dfs3(heights,j,0,v);
        }
        for (int i = 0; i < m2; i++) {
            dfs3(heights,i,n2-1,s);
        }
        for (int j = 0; j < n2; j++) {
            dfs3(heights,m2-1,j,s);
        }
        for (int i = 0; i < m2; i++) {
            for (int j = 0; j < n2; j++) {
                if(v[i][j] && s[i][j]){
                    List<Integer>   path2=new ArrayList<>();
                    path2.add(i);
                    path2.add(j);
                    ret2.add(path2);
                }

            }
        }
        return ret2;
    }
    public void dfs3(int[][] h,int i,int j,boolean b[][]){
        b[i][j]=true;
        for (int k = 0; k < 4; k++) {
            int x=dx2[k]+i;
            int y=dy2[k]+j;
            if(x>=0 && x<m2 && y>=0 && y<n2 && h[x][y]>=h[i][j]&& !b[x][y]){
                dfs3(h, x,y,b);
            }
        }
    }
    //扫雷游戏
    int m4,n4;
    int[] dx4={0,0,1,-1,1,1,-1,-1};
    int[] dy4={1,-1,0,0,1,-1,1,-1};
    public char[][] updateBoard(char[][] board, int[] click) {
        m4=board.length;
        n4=board[0].length;
        int x=click[0];
        int y=click[1];
        if(board[x][y]=='M'){
            board[x][y]='X';
            return board;
        }
        dfs(board,x,y);
        return board;
    }
    public void dfs(char[][] b,int i,int j){
        int count4=0;
        //统计地雷个数
        for (int k = 0; k < 8; k++) {
            int x=dx4[k]+i;
            int y=dy4[k]+j;
            if(x>=0 && x<m4 && y>=0 && y<n4 && b[x][y]=='M'){
                count4++;

            }
        }
        //如果没有地雷,展开周围为展开的
        if (count4==0){
            b[i][j]='B';
            for (int k = 0; k < 8; k++) {
                int x=dx4[k]+i;
                int y=dy4[k]+j;
                if(x>=0 && x<m4 && y>=0 && y<n4 && b[x][y]=='E'){
                    //继续查看其周围是否有雷
                    dfs(b,x,y);
                }
            }
        }else{
            b[i][j]=(char)(count4+'0');
            return ;
        }
    }
}
